//
//  DLTrees.h
//  
//
//  Created by Louis CHU on 19/09/11.
//  Copyright 2011 __MyCompanyName__. All rights reserved.
//

#ifndef DL_TREES_H
#define DL_TREES_H

#include "DLList.h"

namespace dlab {
    namespace core {
        
        //****************************************************************************************************************
#pragma mark -
#pragma CBinaryTreeNode
        template <class T>
        class CBinaryTreeNode: public INode<T>, public CCollection<T>
        {
            private:
            protected:
            T               _value;

            CBinaryTreeNode<T> *      _parent;
            CBinaryTreeNode<T> *      _left ;
            CBinaryTreeNode<T> *      _right;
            
            INode<T> *      _previous;
            INode<T> *      _next;
            INode<T> *      _last;
    
        public:
            CBinaryTreeNode(T value): INode<T>(), CCollection<T>(),_value(value),_parent(0), _left(0), _right(0), _previous(0), _next(_left), _last(this){}
            virtual ~ CBinaryTreeNode(){}
            
            bool isLeaf() { return !_left && !_right; }
            
            T      getValue() const { return _value; }
            void   setValue (T  value)  { _value = value; }

            CBinaryTreeNode<T> *    getParent() const { return _parent; }
            void                    setParent (CBinaryTreeNode<T> * parent)  { _parent = parent; }
            
            CBinaryTreeNode<T> *    getLeft() const { return _left; }
            void                    setLeft (CBinaryTreeNode<T> * left)  
            { 
                INode<T> * nextTemp = _next;
                _next = left;
                left->getLast()->setNext(nextTemp);
                if (!nextTemp) _last = left->getLast();
                _left = left;
            }
            
            CBinaryTreeNode<T> *    getRight() const { return _right; }
            void                    setRight (CBinaryTreeNode<T> * right)  
            { 
                if (_right) 
                {
                    if (_right->getPrevious())
                    {
                        _right->getPrevious()->setNext(right);
                        right->setNext(_right->getNext());
                    }
                    else
                    {
                        //Exception: right must have the previous
                    }
                }
                else
                {
                    INode<T> * nextTemp = _last->getNext();
                    _last->setNext(right);
                    _last = right->getLast();
                    right->setNext(nextTemp);
                }
                _right = right; 
            }
            
            INode<T> *   getPrevious() const { return _previous; }
            void         setPrevious (INode<T> * previous)  { _previous = previous; }
            
            INode<T> *   getNext() const { return _next; }
            void         setNext (INode<T> * next)  
            { 
                if(_next) _next->setPrevious(next);
                _next = next;
                if(next) next->setPrevious(this);
            }
            
            INode<T> * getLast() const { return _last; }
            void       setLast (INode<T> * last)  { _last = last; }
        };
        
        //****************************************************************************************************************
#pragma mark -
#pragma CBinarySearchTreeNode
        
        template <class T>
        class CBinarySearchTreeNode: public CBinaryTreeNode<T>
        {
            
        protected:
            void doInsertNode (CBinaryTreeNode<T> * node)
            {
                CBinaryTreeNode<T> * itNode = this;
                while (itNode && !itNode->isLeaf()) 
                {
                    
                    if (itNode->getValue() > node->getValue())
                    {
                        if (itNode->getLeft()) {
                            itNode = itNode->getLeft();
                        }
                        else
                        {
                            itNode->setLeft (node);
                            return;
                        }
                    }
                    else
                    {
                        if (itNode->getRight()) {
                            itNode = itNode->getRight();
                        }
                        else
                        {
                            itNode->setRight (node);
                            return;
                        }
                    }
                }
                
                if (itNode->getValue() > node->getValue())
                {
                    itNode->setLeft (node);
                }
                else
                {
                    itNode->setRight (node);
                }
            }
                        
        public:
            CBinarySearchTreeNode(T value): CBinaryTreeNode<T>(value){}
            virtual ~ CBinarySearchTreeNode(){}
            
        };
        //****************************************************************************************************************
#pragma mark -
#pragma CBalancedBinarySearchTreeNode
        template <class T>
        class CBalancedBinarySearchTreeNode: public CBinarySearchTreeNode<T>
        {
        private:
                       
        protected:
                        
            void normalize() 
            {
                INode<T> * itNode = this;
                while (itNode) {
                    itNode->doNormalize();
                    itNode = itNode->getNext();
                }
            }
            
            void doInsert (T value)
            {
                CBinaryTreeNode<T> * node = new CBalancedBinarySearchTreeNode<T>(value);
                this->doInsertNode(node);
                this->normalize();
            }
            
            void doClear()  {}

            
        public:
            CBalancedBinarySearchTreeNode (T value): CBinarySearchTreeNode<T>(value) {}
            ~CBalancedBinarySearchTreeNode(){}
            
            void doNormalize()
            {
                
            }

           
            
        };
        
        //****************************************************************************************************************
//        #pragma mark -
//        #pragma CBalancedBinarySearchTreeNode
//        template <class T>
//        class CBalancedBinarySearchTreeNode
//        {
//        private:    
//            //------------------------------------------------------------------
//            //PRIVATE VARIABLES
//            T                                        _element;
//            CBalancedBinarySearchTreeNode<T> *       _parent;
//            CBalancedBinarySearchTreeNode<T> *       _left;
//            CBalancedBinarySearchTreeNode<T> *       _right;
//            int                                      _size;
//            //------------------------------------------------------------------
//            //PRIVATE METHODS
//            int size (CBalancedBinarySearchTreeNode<T> * node)
//            {
//                if (node)   return node->getSize();
//                else        return 0;
//            }
//            //------------------------------------------------------------------
//            void addSize (int different)
//            {
//                if (different != 0) 
//                {
//                    CBalancedBinarySearchTreeNode<T> * itNode = this;
//                    while (itNode)
//                    {
//                        int size = itNode->getSize();
//                        itNode->setSize (size+different);
//                        itNode = itNode->getParent();
//                    }
//                }
//            }
//            //------------------------------------------------------------------
//            void insert (CBalancedBinarySearchTreeNode<T> * newNode)
//            {
//                CBalancedBinarySearchTreeNode<T> * itNode = this;
//                while (itNode && !itNode->isLeaf()) 
//                {
//                    
//                    if (itNode->getElement() > newNode->getElement())
//                    {
//                        if (itNode->getLeft()) {
//                            itNode = itNode->getLeft();
//                        }
//                        else
//                        {
//                            itNode->setLeft (newNode);
//                            return;
//                        }
//                        
//                    }
//                    else
//                    {
//                        if (itNode->getRight()) {
//                            itNode = itNode->getRight();
//                        }
//                        else
//                        {
//                            itNode->setRight (newNode);
//                            return;
//                        }
//                    }
//                }
//                
//                if (itNode->getElement() > newNode->getElement())
//                {
//                    itNode->setLeft (newNode);
//                }
//                else
//                {
//                    itNode->setRight (newNode);
//                }
//            }
//            //------------------------------------------------------------------
//
//        public:
//            //------------------------------------------------------------------
//            //CONSTRUCTOR
//            //CBalancedBinarySearchTreeNode() : _element(0), _parent(0), _left(0), _right(0), _size(0) {}
//            CBalancedBinarySearchTreeNode( T element) : _element(element), _parent(0), _left(0), _right(0), _size(1) {}
//            ~CBalancedBinarySearchTreeNode(){}
//            //------------------------------------------------------------------
//            //METHODS
//            bool isLeaf()
//            {
//                //return true;
//                return !_left && !_right;
//            }
//            //------------------------------------------------------------------
//            void insert (T element)
//            {
//                CBalancedBinarySearchTreeNode<T> * newNode = new CBalancedBinarySearchTreeNode<T> (element);
//                insert (newNode);
//            }
//            //------------------------------------------------------------------
//
//            CBalancedBinarySearchTreeNode<T> * getMax() const
//            {
//                CBalancedBinarySearchTreeNode<T> * itNode = this;
//                while (itNode->getRight()) {
//                    itNode = itNode->getRight();
//                }
//                return itNode;
//            }
//            //------------------------------------------------------------------
//            CBalancedBinarySearchTreeNode<T> * getMin() const
//            {
//                CBalancedBinarySearchTreeNode<T> * itNode = this;
//                while (itNode->getLeft()) {
//                    itNode = itNode->getLeft();
//                }
//                return itNode;
//            }
//
//            //------------------------------------------------------------------
//            //PROPRIETIES
//            T getElement() { return _element; } 
//            void  setElement (T element) { _element = element; }
//            //------------------------------------------------------------------
//            CBalancedBinarySearchTreeNode<T> * getParent() const { return _parent; }
//            void  setParent (CBalancedBinarySearchTreeNode<T> * parent) { _parent = parent; }
//            //------------------------------------------------------------------
//            CBalancedBinarySearchTreeNode<T> * getLeft() const { return _left; }
//            void  setLeft (CBalancedBinarySearchTreeNode<T> * left) 
//            { 
//                addSize(size(left) - size(_left));
//                _left = left; 
//            }
//            //------------------------------------------------------------------
//            CBalancedBinarySearchTreeNode<T> * getRight() const { return _right; }
//            void setRight (CBalancedBinarySearchTreeNode<T> * right) 
//            { 
//                addSize (size(right) - size(this->_right));
//                _right = right; 
//            }
//            //----------------------------------------
//
//            int getSize() const { return _size; } 
//            //----------------------------------------
//            void setSize (int size) { _size = size; }
//        };
        
    }
}

#endif
